Method: scanRemaining(int, int, int)

1: package de.fhdw.gaming.ipspiel23.c4.domain.impl.evaluation;
2:
3: import java.util.Set;
4:
5: import de.fhdw.gaming.ipspiel23.c4.domain.C4Direction;
6: import de.fhdw.gaming.ipspiel23.c4.domain.IC4SolutionSlim;
7: import de.fhdw.gaming.ipspiel23.c4.domain.impl.C4BoardSlim;
8: import de.fhdw.gaming.ipspiel23.c4.domain.impl.C4SolutionSlim;
9:
10: import static de.fhdw.gaming.ipspiel23.c4.domain.impl.C4BoardSlim.EMPTY_TOKEN;
11:
12: /**
13: * A {@link C4SolutionAnalyzer} that analyzes the board vertically (columns).
14: */
15: public class C4SolutionAnalyzerVertical extends C4SolutionAnalyzer {
16:
17: /**
18: * A blacklist containing all column indexes which are not part of a solution.
19: */
20: private final boolean[] isColumnBlacklisted;
21:
22: /**
23: * Creates a new {@link C4SolutionAnalyzerVertical}.
24: * @param board The board to analyze.
25: */
26: public C4SolutionAnalyzerVertical(final C4BoardSlim board) {
27: super(board, C4Direction.NORTH);
28: isColumnBlacklisted = new boolean[colMax()];
29: }
30:
31: @Override
32: public void resetCache() {
33: for (int i = 0; i < isColumnBlacklisted.length; i++) {
34: isColumnBlacklisted[i] = false;
35: }
36: }
37:
38: @Override
39: public IC4SolutionSlim tryFindFirstSolution(final IC4SolutionSlim currentSolution, final boolean updateCache) {
40:
41: if (currentSolution != null) {
42: return currentSolution;
43: }
44:
45: // search columns (bottom to top)
46: // count column by column, bottom to top from left to right for faster matches
47: for (int col = 0; col < colMax(); col++) {
48: // skip columns that are full and of which we know that they don't contain a solution.
49: if (isColumnBlacklisted[col]) {
50: continue;
51: }
52: // continue with next column when we start finding empty fields (gravity)
53: boolean inAir = false;
54: int count = 0;
55: int lastToken = 0;
56:
57: for (int row = rowMax() - 1; row >= 0 && !inAir; row--) {
58: final int token = board().getTokenUnsafe(row, col);
59: count = countConsecutivesBranchless(count, token, lastToken);
60: if (count >= targetCount()) {
61: return scanRemaining(token, row, col);
62: }
63: lastToken = token;
64: inAir = token == EMPTY_TOKEN;
65: }
66: // add column to blacklist iff we broke out of the loop
67: // because the row index was < 0 (column full)
68: // and we're allowed to update the cache
69: isColumnBlacklisted[col] = updateCache && !inAir;
70: }
71: return null;
72: }
73:
74: @Override
75: public void findAllSolutions(final Set<IC4SolutionSlim> resultSet, final boolean updateCache) {
76: // search columns (bottom to top)
77: // count column by column, bottom to top from left to right for faster matches
78: for (int col = 0; col < colMax(); col++) {
79: // skip columns that are full and of which we know that they don't contain a solution.
80: if (isColumnBlacklisted[col]) {
81: continue;
82: }
83: // continue with next column when we start finding empty fields (gravity)
84: boolean inAir = false;
85: int count = 0;
86: int lastToken = 0;
87: boolean colContainsSolution = false;
88: int row = rowMax() - 1;
89: for (; row >= 0 && !inAir; row--) {
90: final int token = board().getTokenUnsafe(row, col);
91: count = countConsecutivesBranchless(count, token, lastToken);
92: if (count >= targetCount()) {
93: final C4SolutionSlim solution = scanRemaining(token, row, col);
94: resultSet.add(solution);
95: count = 0;
96: colContainsSolution = true;
97: // skip to end of the match
98: row = solution.getRowIndexEnd();
99: }
100: lastToken = token;
101: inAir = token == 0;
102: }
103: // this column is blacklisted iff
104: // 1. We are allowed to update the cache
105: // 2. we never reached an empty field (!inAir == column is full)
106: // 3. this column doesn't contain a solution
107: isColumnBlacklisted[col] = updateCache && !inAir && !colContainsSolution;
108: }
109: }
110:
111: @Override
112: protected C4SolutionSlim scanRemaining(final int token, final int startRow, final int startCol) {
113: int row = startRow - 1;
114:• while (row >= 0 && board().getTokenUnsafe(row, startCol) == token) {
115: row--;
116: }
117: // revert last change to get inclusive upper bound
118: row++;
119: return solutionOf(token, row, startCol, board().getMinimumSolutionSize() + startRow - row);
120: }
121: }